CS 5010: Problem Set 6

Out: Monday, October 17, 2016

Due: Monday, October 24, 2016 at 600pm local time.

The goal of this problem set is to help you design and use multiply-recursive and mutually-recursive data definitions, and to give you practice using the list abstractions and higher-order functions.

Remember that you must follow the design recipe.

You must use DrScheme's HtDP Intermediate Student Language with Lambda.

As usual, the rubric for grading is here. Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, halting measure (when needed), strategy, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS06.

You must also turn in a call graph for your program. As in the preceding problem set, this consists of a diagram showing which functions call which, so we (and you) can see the overall structure of your program. You may draw the diagram using a tool or by hand. Turn this in as a text file, pdf, jpg, or Racket file. Call your file call-tree with an appropriate suffix, and bring a paper copy to your codewalk.

You must include a halting measure for every function that calls itself either directly or indirectly. Be prepared to explain how your halting measure decreases around every cycle in the call graph for that function.

For all universe programs, you may assume that the mouse is never dragged or moved outside of the canvas. Once the mouse enters the canvas, if the mouse ever leaves the canvas, then the behavior of your system is unspecified.

Required Exercise

1. The canvas starts empty. Its size is 500 pixels wide by 400 pixels high.
2. Nodes of the tree are rendered either as circles or squares of a fixed size. The circles should be of radius 20, and the squares should appear the same size as the circles. your system should allow you to change the size of the nodes for the next run by changing a single line of your code.
3. Unselected nodes should be rendered in outline mode; selected nodes should be rendered in solid mode.
4. When the tree is displayed, there should be a straight blue line from the center of a node to the center of each of its sons.
5. You can select a node by clicking anwyhere inside it. Selected nodes are displayed as green solid circles. Clicking on a node selects only the node, not any of its subtrees. If the mouse is clicked in the overlap of two or more nodes, all the nodes are selected, even if one node is a son or descendant of the other.
6. Dragging a selected node causes the entire tree rooted at that node to be dragged, using smooth dragging. The relative positions of all the nodes in the subtree should stay the same. It is ok if this action causes some nodes to be moved off the edge of the canvas; if the node is moved again so that they are now back on the canvas, they should reappear in the proper place.
7. Hitting "c" when a node is selected adds a new son to the selected node. The new node should be a circle whose center has an x-coordinate that is 3 radii to the left of the center of the currently leftmost son, and a y-coordinate that is 3 radii down from the center of the parent. If the node has no sons, then hitting "c" should create the node's first son, appearing 3 radii down and directly beneath the node.
8. Hitting "c" when no node is selected creates a new root node that is a circle. The new node should appear in the center of the top of the canvas. The root appears tangent to the top of the canvas and initially has no sons.
9. Hitting "s" at any time should behave like "c", except that the new node created is a square instead of a circle.
10. Hitting "d" when a node is selected deletes the selected node. When a node is deleted, its sons become the sons of the parent of the deleted node. If the deleted node is a root node (and therefore has no parent), then its sons become root nodes. See the video for examples.

Here's a demo.

Your solution should provide the following functions:

initial-world : Any -> World
GIVEN: any value
RETURNS: an initial world.  The given value is ignored.

run :  Any -> World
GIVEN: any value
EFFECT: runs a copy of an initial world
RETURNS: the final state of the world.  The given value is ignored.

world-after-mouse-event : World Integer Integer MouseEvent -> World
GIVEN: a World, a location, and a MouseEvent
RETURNS: the state of the world as it should be following the given mouse event at that location.

world-after-key-event : World KeyEvent -> World
GIVEN: a World and a key event
RETURNS: the state of the world as it should be following the given key event
 
world-to-trees : World -> ListOfTree
GIVEN: a World
RETURNS: a list of all the trees in the given world.

tree-to-root : Tree -> Node
GIVEN: a tree
RETURNS: the node at the root of the tree
EXAMPLE: Consider the tree represented as follows:

                 A
                 |
       +---+-----+-----+
       |   |     |     |
       B   C     D     E
           |           |
         +---+      +-----+
         |   |      |     |
         F   G      H     I

If tree-to-root is given the subtree rooted at C, it should return the
data structure associated with node C. This data structure may or may
not include data associated with rest of the tree, depending on
whether you have chosen to represent nodes differently from trees.


tree-to-sons : Tree -> ListOfTree
GIVEN: a tree
RETURNS: the data associated with the immediate subtrees of the given
tree. 
EXAMPLE: In the situation above, if tree-to-sons is given the subtree
rooted at C, it should return a list consisting of the subtree rooted
at F and the subtree rooted at G.

[Note how these examples are expressed.  They are not just tests, but
are constructed to illuminate possible ambiguities or
misunderstandings in the purpose statement.  This is what a good
example does.]


node-to-center : Node -> Posn
RETURNS: the center of the given node as it is to be displayed on the
scene.
Note: this function returns a Posn (an ISL builtin).  This is for the
convenience of the testing framework, and you may or may not wish to
represent the center of the node in this way.

node-to-selected? : Node -> Boolean
RETURNS: true iff the given node is selected.

Hints:

• You will find this problem much easier if you follow the slogan "The Structure of the Program Follows the Structure of the Data" (Lesson 3.4). If you write good data definitions, and follow the templates, you will be led to a good solution. If you stray from the templates, you will create a mess.
• Use the System Design Recipe: get a small subset of your system working first, and then add the other required features, one at a time.
• The specifications talk about Tree and Node, because some students may wish to implement these as different data definitions. If you wish to represent Trees and Nodes as the SAME data structure, that is also permissible.
• The built-in abstraction functions, like map, foldr, and filter, are your friends. Use them wherever it is feasible to do so. As before, you may want to write your functions using explicit recursions, and then rewrite them using the abstractions and higher-order function combination. You will be penalized for recursions in your code that "obviously" could have been replaced by one of the mapping functions. [Meta-Hint: there are a few recursions in the solution that cannot obviously be replaced by mapping functions. Figuring out which these are is your problem!]
• It is likely that you will find a lot of code that is duplicated or almost-duplicated for squares and circles. The best solutions will cut down this duplication by applying Generalization as described in Module 5.
• Most likely you will want to use scene+line from the image library rather than add-line, since the latter changes the dimensions of the image in surprising ways.